> ## Documentation Index
> Fetch the complete documentation index at: https://mintlify.com/octra-labs/pvac_hfhe_cpp/llms.txt
> Use this file to discover all available pages before exploring further.

# Homomorphic operations

> Understanding addition, subtraction, and multiplication on encrypted data

PVAC-HFHE supports homomorphic addition, subtraction, and multiplication, allowing computation on encrypted data without decryption.

## Overview

Homomorphic operations preserve the algebraic structure:

```
Enc(a) ⊕ Enc(b) = Enc(a + b)
Enc(a) ⊗ Enc(b) = Enc(a × b)
```

The server can compute on ciphertexts without knowing the plaintext values or secret key.

<Info>
  All operations are exact (no approximation errors) and work over the 127-bit prime field F\_p.
</Info>

## Addition

Addition is extremely fast: simply concatenate the layer graphs and edge lists.

```cpp theme={null}
Cipher ct_add(const PubKey& pk, const Cipher& A, const Cipher& B);
```

From `include/pvac/ops/arithmetic.hpp:165-188`:

```cpp theme={null}
Cipher ct_add(const PubKey& pk, const Cipher& A, const Cipher& B) {
    Cipher C;
    C.slots = A.slots;
    
    // Add constant terms
    C.c0 = A.c0.empty() ? B.c0 
         : B.c0.empty() ? A.c0 
         : field::Op::add(A.c0, B.c0);
    
    C.L.reserve(A.L.size() + B.L.size());
    C.E.reserve(A.E.size() + B.E.size());
    
    // Copy A's layers
    C.L = A.L;
    uint32_t off = (uint32_t)A.L.size();
    
    // Copy B's layers with offset indices
    std::transform(B.L.begin(), B.L.end(), 
                   std::back_inserter(C.L),
        [off](Layer L) {
            if (L.rule == RRule::PROD) { 
                L.pa += off; 
                L.pb += off; 
            }
            return L;
        });
    
    // Copy edges
    C.E = A.E;
    std::transform(B.E.begin(), B.E.end(), 
                   std::back_inserter(C.E),
        [off](Edge e) { 
            e.layer_id += off; 
            return e; 
        });
    
    guard_budget(pk, C, "add");
    compact_layers(C);
    return C;
}
```

### Why addition is fast

Addition doesn't create new layers or multiply edges. It just:

1. Merges layer lists (adjusting PROD layer parent indices)
2. Concatenates edge lists (adjusting layer IDs)
3. Adds constant terms

**Performance:**

* **Time:** 0.012 ms (12 microseconds)
* **Ciphertext growth:** None (just concatenation)
* **Noise growth:** Linear

<Tip>
  Addition is 10-87× faster than RLWE schemes (BFV/BGV/CKKS) because it requires no polynomial operations.
</Tip>

### Example

```cpp theme={null}
Cipher a = enc_value(pk, sk, 42);
Cipher b = enc_value(pk, sk, 17);

Cipher sum = ct_add(pk, a, b);
// dec_value(pk, sk, sum) == 59
```

## Subtraction

Subtraction is addition with negation:

```cpp theme={null}
Cipher ct_sub(const PubKey& pk, const Cipher& A, const Cipher& B) {
    return ct_add(pk, A, ct_neg(pk, B));
}
```

Negation scales all edge weights and constants by -1:

```cpp theme={null}
Cipher ct_neg(const PubKey& pk, const Cipher& A) {
    return ct_scale(pk, A, fp_neg(fp_from_u64(1)));
}

Cipher ct_scale(const PubKey&, const Cipher& A, const Fp& s) {
    Cipher C = A;
    for (auto& e : C.E)
        e.w = field::Op::mul(e.w, s);
    for (size_t j = 0; j < C.c0.size(); ++j)
        C.c0[j] = fp_mul(C.c0[j], s);
    return C;
}
```

From `include/pvac/ops/arithmetic.hpp:152-163`.

**Performance:** Same as addition (\~0.012 ms).

## Multiplication

Multiplication creates new PROD layers representing cross-products of parent layers.

```cpp theme={null}
Cipher ct_mul(const PubKey& pk, const Cipher& A, const Cipher& B, 
              size_t S = 8);
```

The parameter `S` controls the number of edges per product layer (default: 8).

From `include/pvac/ops/arithmetic.hpp:194-225`:

```cpp theme={null}
Cipher ct_mul(const PubKey& pk, const Cipher& A, const Cipher& B, 
              size_t S = 8) {
    auto a0 = A.c0;  // Constant term from A
    auto b0 = B.c0;  // Constant term from B
    
    // Strip constant terms
    Cipher A_g = A;
    Cipher B_g = B;
    A_g.c0 = field::Op::zeros(A.slots);
    B_g.c0 = field::Op::zeros(B.slots);
    
    uint32_t LA = (uint32_t)A_g.L.size();
    uint32_t LB = (uint32_t)B_g.L.size();
    uint32_t off = LA;
    
    // Create PROD layers for all pairs (la, lb)
    Cipher C = detail::build_product_cipher(pk, A_g, &B_g,
        [LA, LB](auto&& emit) {
            for (uint32_t la = 0; la < LA; ++la)
                for (uint32_t lb = 0; lb < LB; ++lb)
                    emit(la, lb);
        },
        [](const auto& gA, const auto& gB, uint32_t la, uint32_t lb) {
            return field::Op::mul(gA[la], gB[lb]);
        },
        (size_t)LA * LB, S ? S : 1, "mul");
    
    // Add cross terms: a0 * B_g and b0 * A_g
    detail::append_scaled_edges(C.E, B_g.E, a0, off);
    detail::append_scaled_edges(C.E, A_g.E, b0, 0);
    
    // Constant term
    C.c0 = field::Op::mul(a0, b0);
    
    guard_budget(pk, C, "mul");
    compact_layers(C);
    return C;
}
```

### Multiplication algorithm

Given `A = a0 + g_A` and `B = b0 + g_B` where `a0, b0` are constants and `g_A, g_B` are graph parts:

```
A × B = (a0 + g_A) × (b0 + g_B)
      = a0*b0 + a0*g_B + b0*g_A + g_A*g_B
```

**Steps:**

1. **Product layers:** For each pair `(la, lb)` where `la ∈ layers(A)` and `lb ∈ layers(B)`, create a PROD layer:

```cpp theme={null}
Layer make_prod_layer(const PubKey& pk, uint32_t pa, uint32_t pb) {
    auto nonce = make_nonce128();
    return {RRule::PROD, 
            {prg_layer_ztag(pk.canon_tag, nonce), nonce},
            pa < pb ? pa : pb, 
            pa < pb ? pb : pa};
}
```

From `include/pvac/ops/arithmetic.hpp:90-94`.

2. **Repack edges:** For each PROD layer, create `S` new edges that encode the product value:

```cpp theme={null}
auto emit_repack_edges(const PubKey& pk, uint32_t lid, 
                       const Layer& L,
                       const std::vector<Fp>& target, 
                       size_t s) -> std::vector<Edge>
```

Choose `s-1` random edges, then solve for the last edge's weight to match the target sum.

From `include/pvac/ops/arithmetic.hpp:55-88`.

3. **Add cross terms:** Scale B's edges by `a0` and A's edges by `b0`.

4. **Compute constant:** `c0 = a0 * b0`.

### Why multiplication is more expensive

* **Layer growth:** `|L_C| = |L_A| + |L_B| + |L_A| × |L_B|`
* **Edge growth:** New edges for each product layer
* **Compaction:** May trigger edge merging if budget exceeded

**Performance:**

* **Time:** 2.47 ms
* **vs BFV:** 2.9× faster (shallow), 7.4× faster (leveled)
* **vs CKKS:** 14.3× faster

<Note>
  From `benchmarks/README.md:42-50`, PVAC-HFHE multiplication is significantly faster than RLWE schemes for scalar operations.
</Note>

### Example

```cpp theme={null}
Cipher a = enc_value(pk, sk, 6);
Cipher b = enc_value(pk, sk, 7);

Cipher prod = ct_mul(pk, a, b);
// dec_value(pk, sk, prod) == 42

std::cout << "Layers: " << prod.L.size() << "\n";
std::cout << "Edges: " << prod.E.size() << "\n";
```

## Squaring

Squaring is optimized compared to generic multiplication:

```cpp theme={null}
Cipher ct_square(const PubKey& pk, const Cipher& A, size_t S = 8);
```

From `include/pvac/ops/arithmetic.hpp:227-255`:

```cpp theme={null}
Cipher ct_square(const PubKey& pk, const Cipher& A, size_t S = 8) {
    auto a0 = A.c0;
    
    Cipher A_g = A;
    A_g.c0 = field::Op::zeros(A.slots);
    
    uint32_t LA = (uint32_t)A_g.L.size();
    size_t triangular = (size_t)LA * (LA + 1) / 2;
    
    // Only create PROD layers for (la, lb) where la ≤ lb
    Cipher C = detail::build_product_cipher(pk, A_g, nullptr,
        [LA](auto&& emit) {
            for (uint32_t la = 0; la < LA; ++la)
                for (uint32_t lb = la; lb < LA; ++lb)
                    emit(la, lb);
        },
        [](const auto& gA, const auto&, uint32_t la, uint32_t lb) {
            auto prod = field::Op::mul(gA[la], gA[lb]);
            // Double off-diagonal terms
            return la != lb ? field::Op::add(prod, prod) : prod;
        },
        triangular, S ? S : 1, "square");
    
    auto two_a0 = field::Op::add(a0, a0);
    detail::append_scaled_edges(C.E, A_g.E, two_a0, 0);
    C.c0 = field::Op::mul(a0, a0);
    
    guard_budget(pk, C, "square");
    compact_layers(C);
    return C;
}
```

**Optimization:** Only creates `LA*(LA+1)/2` PROD layers instead of `LA²`, exploiting symmetry.

## Constant operations

Operations with public constants are much faster:

### Addition with constant

```cpp theme={null}
Cipher ct_add_const(const PubKey&, const Cipher& A, uint64_t k) {
    Cipher C = A;
    Fp v = fp_from_u64(k);
    for (size_t j = 0; j < C.c0.size(); ++j)
        C.c0[j] = fp_add(C.c0[j], v);
    return C;
}
```

From `include/pvac/ops/arithmetic.hpp:269-275`.

**Free operation:** Only updates constant term, no layer/edge changes.

### Multiplication by constant

```cpp theme={null}
Cipher ct_mul_const(const PubKey& pk, const Cipher& A, uint64_t k) {
    return ct_scale(pk, A, fp_from_u64(k));
}
```

From `include/pvac/ops/arithmetic.hpp:261-263`.

**Fast operation:** Scales all edge weights, no new layers.

### Division by constant

```cpp theme={null}
Cipher ct_div_const(const PubKey& pk, const Cipher& A, const Fp& k) {
    return ct_scale(pk, A, fp_inv(k));
}
```

From `include/pvac/ops/arithmetic.hpp:257-259`.

**Requires field inversion** of the constant.

## Depth and noise growth

### Multiplicative depth

The depth of a ciphertext is the longest path of multiplications from fresh encryptions:

* Fresh encryption: depth 0
* Addition/subtraction: `max(depth(A), depth(B))`
* Multiplication: `depth(A) + depth(B) + 1`

### Noise budget

Noise grows with depth:

```cpp theme={null}
struct Budget {
    static Budget compute(const Params& p, int d) {
        double cap = p.noise_entropy_bits 
                   + p.depth_slope_bits * std::max(0, d);
        // ...
    }
};
```

Default parameters:

* Base: 120 bits
* Growth: 16 bits per depth
* At depth 5: 120 + 16\*5 = 200 bits

<Warning>
  When noise budget is exhausted, decryption will fail. The PoC supports depth up to \~5 before ciphertext size becomes impractical.
</Warning>

## Performance comparison

From `benchmarks/README.md:42-72`:

### Scalar multiplication

| Scheme | Time (ms) | vs PVAC-HFHE |
| - | - | - |
| PVAC-HFHE | 2.47 | 1.0× |
| BFV (shallow) | 7.23 | 2.9× slower |
| BFV (leveled) | 18.28 | 7.4× slower |
| BGV | 17.61 | 7.1× slower |
| CKKS | 35.23 | 14.3× slower |

### Scalar addition

| Scheme | Time (ms) | vs PVAC-HFHE |
| - | - | - |
| PVAC-HFHE | 0.012 | 1.0× |
| BFV | 0.124 | 10× slower |
| BGV | 0.552 | 46× slower |
| CKKS | 1.050 | 87× slower |

<Info>
  PVAC-HFHE excels at shallow circuits (depth 1-2) with scalar operations, significantly outperforming RLWE schemes.
</Info>

## Ciphertext management

### Edge budget

When ciphertext edges exceed the budget (default: 1,200,000), automatic compaction triggers:

```cpp theme={null}
void guard_budget(const PubKey& pk, Cipher& C, const char* ctx) {
    if (C.E.size() > pk.prm.edge_budget) {
        compact_edges(pk, C);
    }
}
```

### Compaction

Merges edges pointing to the same (layer, index, sign):

```cpp theme={null}
void compact_edges(const PubKey& pk, Cipher& C) {
    C.E = reduction::merge(
        alg::Carrier<Edge>{ std::move(C.E) }, pk).unwrap();
}
```

From `include/pvac/ops/encrypt.hpp:658-660`.

Also removes unused layers:

```cpp theme={null}
void compact_layers(Cipher& C);
```

## Code examples

### Polynomial evaluation

```cpp theme={null}
// Compute f(x) = 3x³ + 2x² + 5x + 7
Cipher eval_poly(const PubKey& pk, const Cipher& x) {
    Cipher x2 = ct_square(pk, x);           // x²
    Cipher x3 = ct_mul(pk, x2, x);          // x³
    
    Cipher term3 = ct_mul_const(pk, x3, 3); // 3x³
    Cipher term2 = ct_mul_const(pk, x2, 2); // 2x²
    Cipher term1 = ct_mul_const(pk, x, 5);  // 5x
    
    Cipher sum = ct_add(pk, term3, term2);
    sum = ct_add(pk, sum, term1);
    sum = ct_add_const(pk, sum, 7);
    
    return sum;
}
```

### Dot product

```cpp theme={null}
// Compute ⟨a, b⟩ = a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1]
Cipher dot_product(const PubKey& pk, 
                   const std::vector<Cipher>& a,
                   const std::vector<Cipher>& b) {
    assert(a.size() == b.size());
    
    std::vector<Cipher> prods;
    for (size_t i = 0; i < a.size(); ++i) {
        prods.push_back(ct_mul(pk, a[i], b[i]));
    }
    
    Cipher sum = prods[0];
    for (size_t i = 1; i < prods.size(); ++i) {
        sum = ct_add(pk, sum, prods[i]);
    }
    
    return sum;
}
```

## Next steps

<CardGroup cols={2}>
  <Card title="Security" icon="shield" href="/concepts/security">
    Understand the LPN-based security model
  </Card>

  <Card title="API reference" icon="code" href="/api/ops/arithmetic">
    Explore the complete API
  </Card>
</CardGroup>


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.